import java.util.Arrays;

/**
 * 时间复杂度：O(N^2)
 * 空间复杂度：O(1)
 * 不管有序无序，时间复杂度都是O(N^2)
 * 稳定性：非稳定
 */
public class SelectSort {
    public static void selectSort(int[] array) {
        for(int i = 0; i < array.length; i++) {
            int minIndex = i;
            for(int j = i+1; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            Swap(array,minIndex,i);
        }
    }

    public static void selectSort2(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while(left < right) {
            int minIndex = left;
            int maxIndex = left;
            for(int i = left+1; i <= right; i++) {
                if(array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if(array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            Swap(array,minIndex,left);
            if(maxIndex == left) {
                maxIndex = minIndex;
            }
            Swap(array,maxIndex,right);
            left++;
            right--;
        }
    }

    public static void Swap(int[] array,int x,int y) {
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }


    public static void main(String[] args) {
        int[] array = {4,2,6,8,1};
        SelectSort.selectSort2(array);
        System.out.println(Arrays.toString(array));
    }
}
